1. Field of the Invention
The present invention provides a Viterbi decoder, and more particularly, a Viterbi decoder with less selector modules in response to taps of a partial response for preventing from signal delays and increasing efficiency when decoding.
2. Description of the Prior Art
Partial response maximum likelihood, or PRML, has been utilized in a plurality of digital signal processes, which modulates original signals with a partial response, so as to output modulated signals through a channel to a receiver of maximum likelihood sequence estimation, or MLSE, and a Viterbi detector is one of those circuits detecting convolution codes based on MLSE.
As those skilled in the art recognized, a communication channel always includes additive white Gaussian noise, (or AWGN), or other interferences, so that a communication system encodes data before transmitting for decreasing detection errors. For example, applied a specific algorithm, data is convoluted to more bits before being transmitted. Therefore, based on the algorithm, the communication system can detect whether the received data is correct or not, and even return wrong bits in the data to right.
Please refer to FIG. 1, which illustrates a block diagram of a prior art Viterbi decoder 10. The Viterbi decoder 10 includes a branch metric unit 12, an add-compare-select unit 14, a path memory module 18, a path metric memory module 16 and an output selector 20. The branch metric unit 12 receives a sequence of signals DTi, and transmits the signals DTi to the add-compare-select unit 14 through a plurality of branch paths according to a default setting of the Viterbi decoder 10. The add-compare-select unit 14 determines path metrics of the signals DTi by means of Viterbi algorithm based on MLSE, and outputs the path metrics to the path metric memory module 16. Meanwhile, the add-compare-select unit 14 calculates a plurality of state values and outputs to the path memory module 18. The path memory module 18 includes a plurality of selector modules in a series connection. The output selector 20 determines a sequence of output signals DTo according to signals outputted from the path memory module 18. As to operations of the Viterbi decoder 10, take tap number of the partial response being 3, or PR(1,2,1), for example. In this case, the Viterbi decoder 10 includes four states, and the branch metric unit 12 transmits the signals DTi to the add-compare-select unit 14 through six branches. Please refer to FIG. 2 and FIG. 3. FIG. 2 illustrates a state diagram of Viterbi algorithm with four states S00, S01, S10, and S11, while FIG. 3 illustrates a schematic diagram of the path memory module 21 corresponding to the state diagram in FIG. 2.
As shown in FIG. 2, input values (or original data) 0 and 1 in each state generate corresponding output values (or coded signals), which can be 4, 2, −2, and −4. After the coded signals is sent to a communication channel, the coded signals may suffer interference, yet the add-compare-select unit 14 can determine a result closest to the original data according to Viterbi algorithm. In FIG. 3, the path memory module 21 includes eleven selector modules 22 for decoding input signals having ten bits. Each selector module 22 includes four registers 24 and two selectors 26. The selectors 26 determine the output signals according to select signals S0 & S1 provided by the add-compare-select unit 14. Formulas for the add-compare-select unit 14 to calculate path metric values for determining the select signals S0 & S1 are as follow:P(t,S00)=min{(P(t−1,S00)+B(t,−4)),(P(t−1,S10)+B(t,−2))}P(t,S01)=P(t−1,S00)+B(t,−2)P(t,S10)=P(t−1,S11)+B(t,−2)P(t,S11)=min{(P(t−1,S01)+B(t,2)),(P(t−1,S11)+B(t,4))}
                              S          ⁢                                          ⁢          0                =                ⁢                              0            ⁢                                                  ⁢            for            ⁢                                                  ⁢                          (                                                P                  ⁡                                      (                                                                  t                        -                        1                                            ,                                              S                        ⁢                                                                                                  ⁢                        00                                                              )                                                  +                                  B                  ⁡                                      (                                          t                      ,                                              -                        4                                                              )                                                              )                                <                      (                                          P                ⁡                                  (                                                            t                      -                      1                                        ,                                          S                      ⁢                                                                                          ⁢                      10                                                        )                                            +                              B                ⁡                                  (                                      t                    ,                                          -                      2                                                        )                                                      )                                                  =                ⁢                  1          ⁢                                          ⁢          for          ⁢                                          ⁢          otherwise                                                  S          ⁢                                          ⁢          1                =                ⁢                              0            ⁢                                                  ⁢            for            ⁢                                                  ⁢                          (                                                P                  ⁡                                      (                                                                  t                        -                        1                                            ,                                              S                        ⁢                                                                                                  ⁢                        01                                                              )                                                  +                                  B                  ⁡                                      (                                          t                      ,                      2                                        )                                                              )                                <                      (                                          P                ⁡                                  (                                                            t                      -                      1                                        ,                                          S                      ⁢                                                                                          ⁢                      11                                                        )                                            +                              B                ⁡                                  (                                      t                    ,                    4                                    )                                                      )                                                  =                ⁢                  1          ⁢                                          ⁢          for          ⁢                                          ⁢          otherwise                    where P(t) is a path metric value, and B(t) is path value.
The above states of a Trellis tree and related operations are well-known in the art, so this paragraph will not disclose further. As long as the path metric values and the select signals S0 & S1 are determined continuously, the output signals DTo can be obtained.
For example, continuing with FIG. 2 and FIG. 3, please refer to FIG. 4, which illustrates a table of signals DTi and DTo of the Viterbi decoder 10 having four states. In FIG. 4, original signals Sii are encoded to the signals DTi with the partial response. After receiving the signals DTi, the Viterbi decoder 10 having four states decodes the signals DTi to the signals DTo according to the above-mentioned Viterbi algorithm. As shown in FIG. 4, the sequence of the signals DTo delays two bits comparing to the original signals Sii (that is, the sequence of the signals DTo lacks the first and second bits of the signals Sii). Therefore, the prior art Viterbi decoder 10 cannot decode the first two bits of the original signals Sii. In addition, the question marks of the signals DTo in FIG. 3 means that the Viterbi decoder 10 has not yet converged, so that as long as the longer sequence of signals DTi is received, the correct original signals Sii can be decoded.
However, if the sequence of the signals DTi becomes much longer, the prior art Viterbi algorithm needs more memory space, meaning that the path memory module 21 should include more selector modules 22 for generating the convergent output signals DTo, so that the prior art Viterbi decoder 10 costs a lot of system resources for generating a reliable result, but the result delays some bits comparing to the original signal. For example, a path memory module of a Viterbi decoder of a prior art high-density digital-versatile-disc drive, or HD-DVD drive, should include twenty selector modules, but output signals of the Viterbi decoder of the HD-DVD drive delay three bits comparing to the original signals.
In summary, delays of the output signals and demands of the selector modules cause the prior art Viterbi decoder to be unable to increase efficiency and to waste system resources.